package com.lee.algorithm.recursion;

/***
 * @description: 数字字符串转字母字符串
 *      规定1和A对应、2和B对应、3和C对应...
 *      那么一个数据字符串比如"111"，就可以转换为"AAA"、"KA"和"AK"
 *      给定一个只有数字字符串组成的字符串str，返回有多少种转换结果
 * @author : 青石路
 * @date: 2022/1/1 19:15
 */
public class NumberConvertLetter {

    /**
     * i之前位置的数字字符如何转换已经做过决定了
     * 对 i 位置进行尝试，i以及之后位置有多少种转换结果
     * @param chs
     * @param i
     * @return
     */
    public static int choice(char[] chs, int i) {
        if (i == chs.length) {
            // 最后一个位置，只有一种选择
            return 1;
        }
        if (chs[i] == '0') {
            // 这种尝试不行，不符合规则
            return 0;
        }
        if (chs[i] == '1') {
            // i位置的数字字符作为单独的部分，后续有多少种转换
            int res = choice(chs, i + 1);
            if (i + 1 < chs.length) {
                // i 和 (i+1)两个位置上的数字字符一起作为一个单独的部分，后续有多少种转换
                res += choice(chs, i + 2);
            }
            return res;
        }
        if (chs[i] == '2') {
            // i位置的数字字符作为单独的部分，后续有多少种转换
            int res = choice(chs, i+1);
            if (i + 1 < chs.length && (chs[i+1] >= '0' && chs[i+1] <= '6')) {
                // i 和 (i+1)两个位置上的数字字符一起作为一个单独的部分，后续有多少种转换
                res += choice(chs, i + 2);
            }
            return res;
        }
        return choice(chs, i + 1);
    }

    public static void main(String[] args) {
        String numberStr = "1211";
        int converts = choice(numberStr.toCharArray(), 0);
        System.out.println(converts);
    }
}
